\section{Introduction} \label{sec:intro}
LWE (Learning with Errors) is a generalisation for large moduli of the well-known LPN (Learning Parity with Noise) problem. It was introduced by Regev in~\cite{regev:acm09} and has provided cryptographers with a remarkably flexible tool for building cryptosystems. For example, Gentry, Peikert and Vaikuntanathan presented in~\cite{GPV08} LWE-based constructions of trapdoor functions and identity-based encryption. Moreover, in his recent seminal work Gentry \cite{Gentry09:phd} resolved one of the longest standing open problems in  cryptography with a construction related to LWE: the first fully homomorphic encryption scheme. This was followed by further constructions of (fully) homomorphic encryption schemes based on the LWE problem, e.g. \cite{albrecht-farshim-faugere-perret:asiacrypt2011,Brakerski2011a}. 
Reasons for the popularity of LWE as a cryptographic primitive include its simplicity as well as convincing theoretical arguments regarding its hardness, namely, a  reduction from worst-case lattice problems, such as the (decision) Shortest Vector Problem (GapSVP) and Short Independent Vectors Problem (SIVP), to average-case LWE \cite{regev:acm09,brakerski-langlois-peikert-regev-stehle:stoc13}.  
\begin{definition}[LWE~\cite{regev:acm09}]\label{def:lwe}Let $n, q$ be positive integers, $\chi$ be a probability distribution on $\Z$ and \svec be a secret vector following the uniform distribution on $\Zq^n$. We denote by $\Ldis$ the probability distribution on $\Zq^n \times \Zq$ obtained by choosing $\mathbf{a}$ from the uniform distribution on $\Zq^n$, choosing $e \in \Z$ according to $\chi$, and returning  $(\avec,c)=(\avec,\dotp{\avec}{\svec}+ e) \in \Zq^n \times \Zq.$\\
-- \textnormal{Search-LWE} is the problem of finding $\svec \in \Zq^n$ given pairs $(\avec_i, c_i) \in \Zq^n \times \Zq$ sampled according to $\Ldis$.\\
-- \textnormal{Decision-LWE} is the problem of deciding whether pairs $(\avec_i, c_i) \in \Zq^n \times \Zq$ are sampled according to $\Ldis$ or the uniform distribution over $\Zq^n \times \Zq$.
\end{definition}
The modulus $q$ is typically taken to be polynomial in $n$, and $\chi$ is the discrete Gaussian distribution on $\Z$ with mean $0$ and standard deviation $\sigma = \alpha \cdot q$, 
for some $\alpha$.\footnote{It is common in the literature on LWE to parameterise discrete Gaussian distributions by $s = \sigma\sqrt{2\pi}$ instead of $\sigma$. Since we are mainly interested in the ``size'' of the noise, we deviate from this standard in this work.} For these choices it was shown in \cite{regev:acm09,brakerski-langlois-peikert-regev-stehle:stoc13} that if $\sqrt{2\pi} \sigma > 2\sqrt{n}$, then (worst-case) ${\rm GapSVP}-\tildeO{n/\alpha}$ reduces to (average-case) LWE.

\heading{Motivation} While there is a reduction of LWE to (assumed) hard lattice problems \cite{regev:acm09}, little is known about the \emph{concrete} hardness of particular LWE instances. That is, given particular values for $\sigma$, $q$ and $n$, what is the computational cost to recover the secret using currently known algorithms? As a consequence of this gap, most proposals based on LWE do not provide  concrete choices for parameters and restrict themselves to asymptotic statements about security, which can be considered unsatisfactorily vague for practical purposes. In fact we see this lack of precision as one of the several obstacles to the consideration of LWE-based schemes for real-world applications.

\heading{Previous Work} We may classify algorithms for solving LWE into two families. The first family reduces LWE to the problem of finding a short vector in the (scaled) dual lattice (commonly known as the Short Integer Solution (SIS) problem) constructed from a set of LWE samples. The second family solves the Bounded Distance Decoding (BDD) problem in the primal lattice. For both families lattice reduction algorithms may be applied. We may either use lattice reduction to find a short vector in the dual lattice or apply lattice reduction and (a variant of) Babai's algorithm to solve BDD \cite{LindnerP10}. Indeed, the expected complexity of lattice algorithms is often exclusively considered when parameters for LWE-based schemes are discussed. However, while the effort on improving lattices algorithms is intense \cite{rueckert-schneider:eprint2010,chen-nguyen:asiacrypt2011,nguyen:eurocrypt2011,gama-nguyen-regev:eurocrypt2010,nguyen-stehle:talgs2009,hanrot-pujol-stehle:crypto2011,DBLP:conf/issac/MorelSV09,DBLP:journals/iacr/PujolS09}, our understanding of the behaviour of these algorithms in high dimensions is still limited. 

On the other hand, combinatorial algorithms for tackling the LWE problem remain rarely investigated from an algorithmic point of view. For example, the main subject of this paper -- the BKW algorithm -- specifically applied to the LWE problem has so far received no treatment in the literature\footnote{However, a detailed study of the algorithm to the LPN case was provided~\cite{FL06}, which in fact heavily inspired this work. The authors of \cite{FL06} conducted a detailed analysis of the BKW algorithm as applied to LPN, while also giving revised security estimates for some HB-type authentication protocols relying on the hardness of LPN.}. However, since the BKW algorithm can be viewed as an oracle producing short vectors in the dual lattice spanned by the $\mathbf{a}_i$ (i.e., it reduces LWE to SIS) it shares some similarities with combinatorial (exact) SVP solvers. Finally, recently a new algorithm for LWE that reduces the problem to BDD but does not make calls to lattice reduction algorithms has been proposed: Arora and Ge \cite{arora-ge:icalp2011} proposed a new algebraic technique for solving LWE. The algorithm has a total complexity (time and space) of $2^{\tildeO{\sigma^2}}$ and is thus subexponential when $\sigma \leq \sqrt{n}$, remaining exponential when $\sigma > \sqrt{n}$. It is worth noting that Arora and Ge achieve the $\sqrt{n}$ hardness-threshold found by Regev~\cite{regev:acm09}, and thus provide a subexponential algorithm precisely in the region where the reduction to GapSVP fails. We note however that currently the main relevance of Arora-Ge's algorithm is asymptotic as the constants hidden in $\tildeO{\cdot}$ are rather large \cite{SCC12_AG}; it is an open question whether one can improve its practical efficiency.

\heading{Contribution} Firstly, we present a detailed study of a dedicated version of the Blum, Kalai and Wasserman (BKW) algorithm~\cite{DBLP:journals/jacm/BlumKW03} for LWE with discrete Gaussian noise. The BKW algorithm is known to have (time and space) complexity $2^{\bigO{n}}$ when applied to LWE instances with a prime modulus polynomial in $n$~\cite{regev:acm09}; in this paper we provide both the leading constant of the exponent in $2^{\bigO{n}}$ and concrete costs of BKW when applied to Search- and Decision-LWE. That is, by studying in detail all steps of the BKW algorithm, we `de-asymptotic-ify' the understanding of the hardness of LWE under the BKW algorithm and provide concrete values for the expected number of operations for solving instances of the LWE problem.  More precisely, we show the following theorem in Section~\ref{subsection:complexity_search}.

\def\informaltheorem{Let $(\avec_i,c_i)$ be samples following $\Ldis$, set $a = \lfloor \log_2(1/(2\alpha)^2)\rceil$, $b = n/a$ and $q$ a prime. Let $d$ be a small constant $0 < d < \log_2(n)$. 
Assume $\alpha$ is such that $q^b = q^{n/a} = q^{n/\lfloor\log_2(1/(2\alpha)^2)\rceil }$ is superpolynomial in $n$. Then, given these parameters, the cost of the BKW algorithm to solve \textnormal{Search-LWE} is
\begin{equation*}
\naddssteponeT+ \left\lceil\frac{q^b}{2}\right\rceil \cdot \left(\gnd +1\right) \cdot d \cdot a + \poly \approx \left(a^2n\right) \cdot \frac{q^b}{2}
\end{equation*}
operations in $\Zq$.
Furthermore, 
\begin{equation*}
\ncallsT + \poly \mbox{ calls to $\Ldis$ and storage of }
\left(\ncallsT \cdot n \right) \mbox{ elements in $\Zq$  are needed}.
\end{equation*} 
}
\begin{theorem}[Search-LWE, simplified]
\informaltheorem
\end{theorem}
We note that the above result is a corollary to our main theorem (Theorem \ref{theorem:complexity1}) which depends on a value $m$. However, since at present no closed form expressing $m$ is known, the above simplified statement avoids $m$ by restricting choices on parameters of the algorithm. We also show the following simple corollary on the algorithmic hardness of Decision-LWE.
\begin{corollary}[Decision-LWE]
Let $(\avec_i,c_i)$ be samples following $\Ldis$, $0 < b \leq n$ be a parameter, $0 < \PrS < 1$ the targeted success rate and $a = \abn$ the addition depth. Then, the expected cost of the BKW algorithm to distinguish $\Ldis$ from random with success probability $\PrS$ is
$$\naddssteponeexactT$$
additions/subtractions in $\Zq$ to produce elimination tables,
$$\naddssteponeexactM \textnormal{ with } m = \PrS/\exp\left(-\frac{\pi^{2} \sigma^{2} 2^{{a + 1}}}{q^{2}}\right)$$
additions/subtractions in $\Zq$ to produce samples. Furthermore,
$\ncallsT + \ncallsM$
calls to $\Ldis$ and storage for
$\nstore$
elements in $\Zq$ are needed.
\end{corollary}
This corollary is perhaps the more useful result for cryptographic applications which rely on Decision-LWE and do not assume a prime modulus $q$. Here, we investigate the search variant first because the decision variant follows easily. However, we emphasize that there are noticeable differences in the computational costs of the two variants. A reader only interested in Decision-LWE is invited to skip Sections~\ref{sec:hypothesis} and \ref{sec:backsubstitution}.

In Section~\ref{sec:parameters}, we apply the BKW algorithm to various parameter choices for LWE from the literature~\cite{regev:acm09,LindnerP10,albrecht-farshim-faugere-perret:asiacrypt2011} and compare with alternative approaches in Section~\ref{sec:comparison}. It appears that the BKW algorithm outperforms known estimates for lattice reduction algorithms when LWE is reduced to SIS (called ``Distinguishing'' in \cite{LindnerP10}) starting in dimension $n \approx 250$ (but, assuming access to an unbounded number of LWE samples). However, reducing LWE to BDD (called ``Decoding'' in \cite{LindnerP10}) and applying a combination of lattice reduction and decoding outperforms BKW for the parameter sets considered in this work.  However, since the concrete behaviour of lattice reduction algorithms is not fully understood, the commonly used running-time estimates tend to be optimistic. In contrast, for combinatorial algorithms such as BKW, we have a much better understanding of the concrete complexity, leading to greater confidence in the recovered bounds. Finally, we report experimental results for small instances of LWE in Section~\ref{sec:implementation}.

\section{Preliminaries}
\label{sec:preliminaries}
\heading{Gaussians} Let $\N{\mu,\sigma^2}$ denote the Gaussian distribution with mean $\mu$ and standard deviation $\sigma$.
The LWE problem considers a discrete Gaussian distribution over $\Z$ which is then reduced modulo $q$. This distribution in $\Zq$ can be obtained by \emph{discretising} the corresponding \emph{wrapped} Gaussian distribution over the reals. To wrap $\N{0,\sigma^2}$ mod $q$, we denote by $p(\phi)$ the probability density function determined by $\sigma$, define the periodic variable $\theta := \phi \bmod q$ and let
\begin{equation}
p'(\theta)=\sum_{k=-\infty}^{\infty}{p(\theta+qk)} \mbox{ for } -q/2 < \theta \leq q/2.
\end{equation}
As $\abs{k}$ increases, the contribution of $p(\theta + qk)$ falls rapidly; in fact, exponentially fast \cite{duembgen-arxiv2010}. Hence, we can pick a point at which we `cut' $p'(\theta)$ and work with this approximation. We denote the distribution sampled according to $p'$ and rounded to the nearest integer in the interval $]\frac{-q}{2},\frac{q}{2}]$ by $\chi_{\alpha,q}$, where $\sigma = \alpha \cdot q$.
That is, 
\begin{equation}
\Pr[X=x]=\int_{x-\frac{1}{2}}^{x+\frac{1}{2}}{p'(t)} dt 
\end{equation}
 We note that, in our cases of interest, we can explicitly compute $\Pr[X=x]$ because both $q$ and $k$ are $\poly$.

We state a straightforward lemma which will be useful in our computations later.
\begin{lemma}\label{lem:noisedist}
Let $X_0,\ldots,X_{m-1}$ be independent random variables, with $X_i \sim \N{\mu, \sigma^2}$. 
Then their sum $X = \sum_{i=0}^{m-1} X_i$ is also normally distributed, with $X \sim \N{m\mu, m \sigma^2}$.
\end{lemma}
In the case of $X_i$ following a discrete Gaussian distribution, it does not necessarily follow that a sum of such random variables is distributed in a way analogous to the statement above. However, throughout this work, we assume that this does hold i.e., that Lemma \ref{lem:noisedist} applies to the discrete Gaussian case - while we do not know how to prove this, this assumption causes no apparent discrepancies in our experimental results. For a detailed discussion on sums of discrete Gaussian random variables, the interested reader is referred to \cite{agrawal-gentry-halevi-sahai:eprint2012}. 

\heading{Computational Model} We express concrete costs as computational costs and storage requirements. We measure the former in $\Zq$ operations and the latter in the number of $\Zq$ elements requiring storage. However, as the hardness of LWE is related to the quantity $n\log q$ \cite{brakerski-langlois-peikert-regev-stehle:stoc13}, relying on these measures would render results for different instances incommensurable. We hence normalise these magnitudes by considering ``bit-operations'' where one ring operation in $\Zq$ is equivalent to $\log_2 q$ such bit operations. The specific multiplier $\log_2 q$ is derived from the fact that the majority of operations are additions and subtractions in $\Zq$ as opposed to multiplications in $\Zq$. In particular, we ignore the cost of ``book keeping'' and of fixed-precision floating point operations occuring during the algorithm (where the precision is typically a small multiple of $n$, cf.\ Section~\ref{sec:parameters}).

We make the assumption that we have unrestricted access to an LWE oracle, allowing us to obtain a large number of independent LWE samples which may not be available in practise. This assumption is usually made for combinatorial algorithms and the Arora-Ge algorithm, while lattice reduction algorithms usually require only a small number of LWE samples. However, as we discuss later, the optimal strategies for employing lattice based approaches for solving LWE appear to require executing a large number of small-advantage executions, each requiring independent LWE samples. While the cryptosystems considered in this work do not provide such an LWE oracle it is known \cite{DBLP:conf/coco/Regev10} that given roughly $n\log q$ LWE samples one can produce many more LWE samples at the cost of an increase in the noise through inter-addition. While employing these approaches would render our proofs inapplicable, it is assumed that in practice similar results would still hold. Similar notions (in the case of LPN) were considered in \cite{FL06}, although, as in this work, the authors did not analyse the impact of these steps.

\heading{Notation} We always start counting at zero, and denote vectors in bold. Given a vector $\mathbf{a}$, we denote by $\avec_{(i)}$ the $i$-th entry in $\avec$, i.e., a scalar, and by $\avec_{(i,j)}$ the subvector of $\avec$ spanning the entries at indices $i,\dots,j-1$. When given a list of vectors, we index its elements by subscript, e.g., $\avec_0,\avec_1, \avec_2$, to denote the first three vectors of the list.
When we write $(\avec_i,c_i)$ we always mean the output of an oracle which should be clear from the context. In particular, $(\avec_i,c_i)$ does not necessarily refer to samples following the distribution $\Ldis$.
